package com.cjx.leetcode.heap;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;
import java.util.PriorityQueue;

/**
 * @author cjx
 * @Description
 * @date 2024/3/29 10:29
 **/
public class E2462 {
    public long totalCost(int[] costs, int k, int candidates) {
        long res = 0;
        PriorityQueue<Integer> left = new PriorityQueue<>();
        PriorityQueue<Integer> right = new PriorityQueue<>();
        Deque<Integer> alternateQueues = new LinkedList<>();
        int size = costs.length;
        //1. 根据candidates搭建前后两个小顶堆
        //搭建规则，根据candidates次数放入堆结构中，右顶堆反向放入
        //1.1 如果长度小于candidates*2则直接搭建一个小顶堆
        if (size <= candidates * 2) {
            right = null;
            for (int cost : costs) {
                left.offer(cost);
            }
            //1.2 如果长度大于candidates*2则将剩余工人放入替补双向队列中
        } else {
            for (int i = 0; i < candidates; i++) {
                left.offer(costs[i]);
            }
            for (int i = size - 1, j = candidates; j > 0; i--, j--) {
                right.offer(costs[i]);
            }
            int start = candidates;
            int end = size - candidates;
            while (start < end) {
                alternateQueues.addLast(costs[start]);
                start++;
            }

        }
        //替补队列规则：1. 左顶堆取一个工人，则队列左出一个补充 2. 右顶堆规则一致
        //2. 取k个工人
        //2.1 分别取左右顶堆堆顶元素比较
        if (right == null) {
            return getLeftRes(left, k, res);
        }
        for (; k > 0; k--) {

            Integer leftMin = left.peek();
            Integer rightMin = right.peek();
            //考虑左右堆有为空的情况
            if (leftMin == null){

                res += getRes(right,alternateQueues,false);
                continue;
            }
            if (rightMin == null){

                res += getRes(left,alternateQueues,true);
                continue;
            }
            //2.3 如果一致则默认取左顶堆的元素
            if (leftMin.equals(rightMin) || leftMin < rightMin) {
                res += getRes(left,alternateQueues,true);
                //2.2 如果不一样则取小的，将其值累加到res中，按替补队列规则补充堆
            } else {
               res += getRes(right,alternateQueues,false);
                }
            }

        //3. 取完所有工人，返回res
        return res;
        }



    private long getLeftRes(PriorityQueue<Integer> left, int k, long res) {
        for (; k > 0; k--) {
            Integer poll = left.poll();
            res += poll;
        }
        return res;
    }

    private long getRes(PriorityQueue<Integer> deep,Deque<Integer> alternateQueues,boolean isLeft){
        Integer poll = deep.poll();
        if (!alternateQueues.isEmpty()){
            if (isLeft){
                deep.offer(alternateQueues.removeFirst());
            }
        }
        return poll;
    }

    public static void main(String[] args) {
        int[] ints = {57,33,26,76,14,67,24,90,72,37,30};
        int res = 0;
        for (int anInt : ints) {
            res+= anInt;
        }
        System.out.println(res);
        System.out.println(new E2462().totalCost(ints,11,2));
    }
}
